МИНИСТЕРСТВО НАУКИ И ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ГУМАНИТАРНЫЙ УНИВЕРСИТЕТ

ИНСТИТУТ ЭКОНОМИКИ, УПРАВЛЕНИЯ И ПРАВА

Факультет управления

Кафедра «Моделирование в экономике и управлении»

А.Г. МАДЕРА

Курс

МАТЕМАТИЧЕСКИЕ МОДЕЛИ В УПРАВЛЕНИИ

Методическое пособие по проведению лабораторных работ

по теме “Линейное программирование”

Лабораторная работа №1

Задачи линейного программирования и их решение средствами Excel

Москва 2004

Лабораторные работы призваны, на практике, помочь студентам применить знания полученные на лекциях и при самостоятельной работе. В качестве программной среды используются средства Microsoft Offis Excel (электронные таблицы MS Offis).

Программные средства Excel - Поиск решения является мощным инструментом решения оптимизационных задач. С их помощью можно найти наилучший вариант использования ограниченных ресурсов, обеспечивающий максимальное значение для одних величин, например, прибыли, или же минимальное - для других, например, затрат.

Использования поиска решения поможет дать ответ на такие вопросы:

· Какая цена или ассортимент товаров обеспечат максимальную прибыль?

· Как не выйти за пределы бюджета?

Порядок выполнения работы

На лабораторную работу каждый студент приносит чистую, неиспользованную дискету МД 3,5'. На этой дискете будут содержаться файлы с исходными данными и результатами по всем выполненным работам.

Задание. Получить вариант задачи у преподавателя. Составить математическую модель задачи. Найти оптимальное решение задачи в Excel и показать результаты поиска решения преподавателю на экране компьютера. Отчет составляет на МД.

Отчет. Отчет по лабораторной работе представляется на дискете студента и должен содержать файл с названием ЛР 1 Вариант №… Отчет (Фамилия № группы).

Состав отчета, записанный на МД:

- математическая модель задачи, предъявляемая преподавателю (может быть написана от руки).

- Рабочий лист Excel с исходными данными и математической моделью, протокол решения задачи, куда входят:

- результаты решения в виде отчета Результаты,

- результаты расчета в виде отчета Устойчивость,

- результаты расчета в виде отчета Пределы

Отчет на МД демонстрируется преподавателю на данном лабораторном занятии.

Сдача лабораторной работы преподавателю – при наличии МД с результатами расчета. Во время сдачи лабораторной работы студент должен уметь проводить анализ полученных результатов по всем формам представления результатов Поиска решения: Результаты, Устойчивость, Пределы.

Лабораторная работа № 1

Тема: Задачи линейного программирования и их решение средствами Excel.

Программное обеспечение: Microsoft Excel

Основные сведения

В большинстве оптимизационных задач зависимости между переменными линейны. Линейность предполагает наличие двух свойств пропорциональности и аддитивности.

1. Пропорциональность означает, что вклад каждой переменной в целевую функцию и общий объем потребления соответствующих ресурсов прямо пропорционален уровню (величине) этой переменной.

Аддитивность заключается в том, что целевая функция представляет собой сумму вкладов от различных переменных. Аналогично левая часть каждого ограничения должна представлять собой сумму расходов, каждое слагаемое которой пропорционально величине соответствующей переменной. Если, например, фирма, производит два конкурирующих вида продукции, увеличение сбыта одного из которых отрицательно сказывается на объеме реализации другого, то такая модель не обладает свойством аддитивности.

Математическую модель задачи линейного программирования в общем виде можно записать в виде:

min (max) W = c₁ x₁ + c₂ x₂ +... + c_n x_n; (целевая функция)

при ограничениях:

a₁₁ x₁ + a₁₂ x₂ + ... + a_1n x_n £ (=, ³) b₁

a₂₁ x₁ + a₂₂ x₂ + ... + a_2n x_n £ (=, ³) b₂

. . .

a_m1 x₁ + a_m2 x₂ + ... + a_mn x_n £ (=, ³) b_m

x_j ³ 0, j=1, 2, ... n

Рассмотрим конкретную задачу:

Задача. Руководство фирмы предполагает производить продукцию двух моделей А₁ и А₂. Их производство ограниченно наличием сырья, временем эксплуатации оборудования и денежными кредитами. Для каждого изделия модели А₁ требуется 0,3 м³ древесины, 0,2 часа работы станков и затратить 1,6 денежных единиц, а для изделия модели А₂ - 0,4 м³ древесины, 0,5 часа работы станков и 1 ден. ед. Фирма может получить от своих поставщиков до 170 м³ древесины в неделю и использовать оборудование в течение 160 часов. На финансирование проекта предполагается выделять 800 ден. ед. Сколько изделий каждой модели следует фирме выпускать в неделю, если каждое изделие модели А₁ должно приносить 2 ден. ед. прибыли, а каждое изделие модели А₂ - 4 ден. ед. прибыли?

Построение математической модели

Переменные. Так как нужно определить объемы производства каждого вида моделей продукции, переменными в модели являются:

х₁ - количество выпущенных за неделю изделий модели А₁,

х₂ - количество выпущенных за неделю изделий модели А₂.

Целевая функция. Так как прибыль от реализации 1-го изделия модели А₁ равна 2 денежным единицам, недельный доход от ее продажи составит 2*х₁ ден. ед. Аналогично доход от реализации х₂ штук изделия модели А₂ составит 4*х₂ ден. ед. в неделю.

При допущении независимости объемов сбыта каждой из моделей общий доход равен сумме двух слагаемых - дохода от продажи модели А₁ и дохода от продажи модели А₂.

Обозначив общий доход через W, можно дать следующую математическую формулировку целевой функции: определить (допустимые) значения х₁ и х₂, максимизирующие величину общего дохода W = 2*х₁ + 4*х₂.

Ограничения. При решении рассматриваемой задачи должны быть учтены ограничения на расход древесины, время эксплуатации оборудования и финансовые возможности фирмы.

Ограничение на расход древесины можно записать следующим образом:

0,3 х₁ + 0,4 х₂ £ 170,

здесь 0,3 х₁ расход древесины на выпуск недельного объема в х₁ изделий модели А₁, а 0,4 х₂ - х₂ изделий модели А₂. Суммарный расход древесины на выпуск двух моделей не может превышать максимально возможный запас древесины в 170 м³.

Ограничение на время использование оборудования можно записать следующим образом:

0,2 х₁ + 0,5 х₂ £ 160,

здесь: 0,2 х₁ - количество часов работы оборудования в неделю для выпуска х₁ изделий модели А, а 0,5 х₂ - х₂ изделий модели В в неделю. Время эксплуатации станков для выпуска обоих моделей не может превышать максимально возможный запас времени работы оборудования в160 часов.

Ограничение на использование финансов можно записать следующим образом:

1,6 х₁ + 1,0 х₂ £ 800,

здесь: 1,6*х₁ - количество денежных ресурсов расходуемых в неделю для выпуска х₁ изделий модели А, а 1,0*х₂ - х₂ изделий модели В в неделю. Сумма затрат на выпуск обоих моделей не может превышать максимально возможный запас финансов.

Поскольку х₁ и х₂ выражают еженедельный объём выпускаемых изделий, то они не могут быть отрицательными, т.е. х₁ ³ 0 и х₂ ³ 0 (условие не отрицательности переменных).

Итак, математическую модель задачи № 1 можно записать следующим образом:

max W= 2 х₁ +4 х₂ (целевая функция) (1)

при ограничениях:

0,3 х₁ + 0,4 х₂ £ 170 (2)

0,2 х₁ + 0,5 х₂ £ 160 (3)

1,6 х₁ + х₂ £ 800 (4)

х₁ ³ 0, х₂ ³ 0 (5)

Процесс решения задачи средствами Microsoft Excel

Вызовите Microsoft Excel. В новой рабочей книге переименуйте "Лист№1" в ЛР 1 Вариант №… Отчет (Фамилия № группы)

Задание Исходных данных задачи

Начиная с ячейки с именем А1 на Листе окна Excel постройте следующую таблицу (рис. 1.):

В ячейки с адресами В2:С4 – двоеточие означает диапазон ячеек, начинающийся с ячейки с адресом В2 и заканчивающийся ячейкой с адресом С4 – заносятся коэффициенты при неизвестных х₁ и х₂ в ограничениях (2)–(4).

После занесения в ячейку числа или формулы необходимо нажать клавишу ENTER.

В ячейки с адресами В5:С5 занесены коэффициенты в целевой функции (1).

В строке Переменные ячейки В6:С6 пусты; в них после решения задачи, будут занесены рассчитанные значения переменных х₁ и х₂ .

В столбце Ограничения в ячейки G2:G4 занесены формулы для расчеты левых частей ограничений (2)–(5). Каждая формула начинается со знака «=». Для введения формулы в ячейку G2, щелкните мышью на ячейке с этим адресом (ячейка будет обведена жирной рамкой). В ячейке напечатайте следующее: =СУММПРОИЗВ(B2:C2;B6:C6). Здесь записано, что числа в ячейках с адресами В2:С2 умножаются на соответствующие им числа в ячейках В6:С6 и затем результаты произведений просуммированы. Тем самым задано ограничение (2). Задание ограничений (3) и (4) содержится в ячейках G3, G4; в них напечатаны напечатайте формулы =СУММПРОИЗВ(B3:C3;B6:C6) и =СУММПРОИЗВ(B3:C3;B6:C6) соответственно.

В ячейку В7 занести формулу =СУММПРОИЗВ(B5:C5;B6:C6), которой записана целевая функция (1). В эту же ячейку бедет занесено вычисленное значение целевой функции.

Решение задачи

Поставить курсор мыши в ячейку В7 и нажать на левую кнопку мыши – туда после решения задачи, будет занесено вычисленное значение целевой функции.

Войти в меню Сервис, выбрать в нем Поиск решения и щелкнуть на нем левой кнопкой мыши. На экране появится диалоговое окно Поиск решения (рис. 2). В поле Установить целевую ячейку занести $B$7. Для этого проще всего установить курсор мыши внутрь ячейки, щелкнуть в ней левой кнопкой мыши, затем щелкнуть мышью на ячейке В7.

Поскольку ищется максимум целевой функции, то после слова Равной выделим Максимальному значению, щелкнув в кружочке мышью.

В поле Изменяя ячейки занесем диапазон $B$6:$C$6 так как именно эти ячейки отведены под значения вычисляемых переменных. Для этого поставим курсор в поле Изменяя ячейки , затем поставим курсор на ячейке В6 и при нажатой левой кнопке мыши переведем курсор на ячейку С6. В поле Изменяя ячейки появится необходимый диапазон ячеек.

В поле Ограничения занесем ограничения (2)–(5). Для этого щелкнем мышью на кнопке Добавить. Появится диалоговое окно Добавление ограничения (рис. 3).

В поле Ссылка на ячейку поставить курсор мыши в поле, затем поставить курсор на ячейку G2, где задана формула ограничения. В среднее поле, щелкнув на кнопке со стрелочкой, занесем соответствующий знак неравенства. В поле Ограничение занесем правую часть ограничения, расположенную в ячейке Е2. Щелкнуть на кнопке ОК. Попадаем снова в поле Поиск решения. Затем повторяя описанные выше действия, заносим остальные ограничения (рис. 2).

Снова в поле Поиск решения (рис. 2). Щелкнуть мышью на кнопке Параметры.

На экране появится диалоговое окно Параметры поиска решения. В этом окне (рис. 4) устанавливаются параметры поиска решения. Здесь отметить квадратики Линейная модель, Неотрицательные значения, Автоматическое масштабирование. Щелкнем на кнопке ОК.

Снова попадаем в диалоговое окно Поиск решения. В этом окне (рис. 2) щелкнем левой кнопкой мыши на кнопку Выполнить. На экран

выводится окно Результаты поиска решения (рис. 5).

Одновременно на Листе экрана также появляются результаты решения задачи (рис. 6): В столбце Ограничения выводятся их рассчитанные значения . В строке переменные – значения рассчитанных переменных х₁ и х₂ . В ячейке с целевой функцией – рассчитанное значение целевой функции.

Итак найдено решение: х₁ = 300, х₂ = 200, Fmax = 1400.

В окне Результаты поиска решения содержится тип отчета: Результаты, Устойчивость, Пределы. Для получения всех видов отчетов надо щелкнуть кнопкой мыши на каждом из них – соответствующие строчки будут закрашены – а затем на ОК. Отчеты отображаются в нижней строке Листа на экране Excel. Для их вызова необходимо щелкнуть на соответствующем отчете.

В отчете по результатам (рис. 7) приведены значения неизвестных и целевой функции, а также данные о выполнении ограничений. В графе Статус указаны связанные и несвязанные переменные.

В отчете по устойчивости (рис. 8) приведены границы устойчивости неизвестных задачи – допустимое увеличение и уменьшение коэффициентов целевой функции, границы устойчивости двойственных оценок. В графе Нормированная стоимость элемент этой графы показывает, на сколько уменшится значение функции, если в решении переменную увеличить на единицу.

В отчете по пределам (рис. 9) показаны нижние и верхние пределы изменения неизвестных и значения целевой функции при этих изменениях.

Рис. 7. Отчет по результатам

Рис. 8 Отчет по устойчивости

Рис. 9. Отчет по пределам

Индивидуальные задания

Задание 1. Небольшая фабрика изготовляет два вида красок: для наружных (№1) и внутренних (№2) работ. Продукция обоих видов поступает в оптовую продажу. Для производства красок используются два исходных продукта – А и В. Максимально возможные суточные запасы этих продуктов составляют 6 и 8 т соответственно. Расходы А и В на 1т соответствующих красок приведены в табл.

Изучение рынка сбыта показало, что суточный спрос на краску для внутренних работ (№2) никогда не превышает спрос на краску для наружных работ (№1) более чем на 1 т. Кроме того, установлено, что спрос на краску № 2 никогда не превышает 2 т в сутки.

Прибыль от реализации одной тонны красок № 1 равна 3 тыс. денежных единиц, а для краски № 2 – 2 тыс. ден. ед.

Исходный продукт	Расход исходных продуктов (в тоннах) на тонну краски		Максимально возможный запас, т
	Краска № 1	Краска № 2
А	1	2	6
В	2	1	8

Какое количество краски каждого вида должна производить фабрика, чтобы доход от реализации продукции был максимальным?

Задание 2. Пошивочное предприятие намечает выпуск двух видов костюмов – мужских и женских. На женский костюм требуется 1 м шерсти, 2м лавсана и 1чел/день трудозатрат. На мужской костюм требуется 3,5 м шерсти, 0,5 м лавсана и 1чел/день трудозатрат. Всего имеется 350 м шерсти, 240 м лавсана и 150 чел/день трудозатрат. Определить сколько костюмов каждого вида необходимо сшить, чтобы обеспечить максимальную прибыль, если прибыль от реализации женского костюма составляет 10 денежных единиц, от мужского – 20 денежных единиц. При этом следует иметь в виду, что необходимо сшить не менее 60 мужских костюмов.

Задание 3. Для производства двух видов изделий А и В предприятие использует три вида сырья. Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в табл. В ней же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое может быть использовано предприятием.

Учитывая, что изделия А и В могут производиться в любых соотношениях (сбыт обеспечен), требуется составить такой план их выпуска, при котором прибыль предприятия от реализации всех изделий является максимальной.

Вид сырья	Нормы расхода сырья (кг) на одно изделие		Общее количество сырья (кг)
	А	В
1	12	4	300
2	4	4	120
3	3	12	252
Прибыль от реализации одного изделия (руб)	30	40

Задание 4. Для производства столов и шкафов мебельная фабрика использует необходимые ресурсы. Нормы затрат ресурсов на одно изделие данного вида, прибыль от реализации одного изделия и общее количество имеющихся ресурсов каждого вида приведены в табл.

Ресурсы	Нормы затрат ресурсов на одно изделие		Общее количество ресурсов
	стол	шкаф
Древесина (м3):
1 вида	0,2	0,1	40
2 вида	0,1	0,3	60
Трудоемкость (человеко-час)	1,2	1,5	371,4
Прибыль от реализации одного изделия (руб)	6	8

Определить, сколько столов и шкафов следует изготовлять, чтобы прибыль от их реализации была максимальной.

Задание 5. Для производства двух видом изделий А и В используется токарное, фрезерное и шлифовальное оборудование. Нормы затрат времени для каждого из типов оборудования на одно изделие данного вида приведены в табл. В ней же указан общий фонд рабочего времени каждого из типов оборудования, а также прибыль от реализации одного изделия.

Найти план выпуска изделий А и В, обеспечивающий максимальную прибыль от их реализации.

Тип оборудования	Затраты времени (оборуд.-час) на обработку одного изделия		Общий фонд полезного рабочего времени оборудования (ч)
	А	В
Фрезерное	10	8	168
Токарное	5	10	180
Шлифовальное	6	12	144
Прибыль от реализации одного изделия (руб)	14	18

Задание 6. На мебельной фабрике из стандартных листов фанеры необходимо вырезать заготовки трех видов в количествах, соответственно равных 24, 31 и 18 шт. Каждый лист фанеры может быть разрезан на заготовки двумя способами. Количество получаемых заготовок при данном способе раскроя приведено в табл. В ней же указана величина отходов, которые получаются при данном способе раскроя одного листа фанеры.

Вид заготовки	Количество заготовок (шт) при раскрое по способу
	1	2
1	2	6
2	5	4
3	2	3
Величина отходов (см2)	12	16

Определить, сколько листов фанеры и по какому способу следует раскроить так, чтобы было получено не меньше нужного количества заготовок при минимальных отходах.

Задание 7. На звероферме могут выращиваться черно-бурые лисицы и песцы. Для обеспечения нормальных условий их выращивания используется три вида кормов. Количество корма каждого вида, которое должны ежедневно получать лисицы и песцы, приведено в табл. В ней же указаны общее количество каждого вида, которое может быть использовано зверофермой, и прибыль от реализации одной шкурки лисицы и песца.

Вид корма	Количество единиц корма, которое ежедневно должны получать		Общее количество корма
	Лисица	Песец
1	2	3	180
2	4	1	240
3	6	7	426
Прибыль от реализации одной шкурки (руб)	16	12

Определить, сколько лисиц и песцов следует выращивать на звероферме, чтобы прибыль от реализации их шкурок была максимальной.

Задача 8. Компания производит полки для ванных комнат двух размеров – А и В. Агенты по продаже считают, что в неделю на рынке может быть реализовано до 550 полок. Для каждой полки типа А требуется 2 м2 материала, а для полки типа В – 3 м2 материала. Компания может получить до 1200 м2 материала в неделю. Для изготовления одной полки типа А требуется 12 мин машинного времени, а для изготовления одной полки типа В – 30 мин; машину можно использовать 160 час в неделю. Если прибыль от продажи полок типа А составляет 3 денежных единицы, а от полок типа В – 4 ден. ед., то сколько полок каждого типа следует выпускать в неделю?

Задача 9. Небольшая фирма производит два вида продукции: столы и стулья. Для изготовления одного стула требуется 3 фута древесины, а для изготовления одного стола – 7 футов. На изготовление одного стула уходит 2 часа рабочего времени, а на изготовление стола – 8 часов. Каждый стул приносит 1 долл. прибыли, а каждый стол – 3 долл. Сколько стульев и сколько столов должна изготовить эта фирма, если она располагает 420 футами древесины и 400 часами рабочего времени и хочет получить максимальную прибыль?

Задача 10. Некоторая фирма выпускает два набора удобрений для газонов: обычный и улучшенный. В обычный набор входит 3 фунта азот- ных, 4 фунта фосфорных и 1 фунт калийных удобрений, а в улучшенный – 2 фунта азотных, 6 фунтов фосфорных и 3 фунта калийных удобрений. Известно, что для некоторого газона требуется по меньшей мере 10 фунтов азотных, 20 фунтов фосфорных и 7 фунтов калийных удобрений. Обычный набор стоит 3 долл., а улучшенный – 4 долл. Какие и сколько наборов удобрений нужно купить, чтобы обеспечить эффективное питание почвы и минимизировать стоимость?

Задача 11. На имеющихся у фермера 400 акрах земли он планирует посеять кукурузу и сою. Сев и уборка кукурузы требует на каждый акр 200 долл. затрат, а сои – 100 долл. На покрытие расходов, связанных с севом и уборкой, фермер получил ссуду в 60 тыс. долл. Каждый акр, засеянный кукурузой, приносит 40 бушелей, а каждый акр, засеянный соей, – 80 бушелей. Фермер заключил договор на продажу, по которому каждый бушель кукурузы принесет ему 3 долл., а каждый бушель сои – 1 долл. Однако, согласно этому договору, фермер обязан хранить убранное зерно в течение нескольких месяцев на складе, максимальная вместимость которого равна 21 тыс. бушелей. Фермеру хотелось бы знать, сколько акров нужно засеять каждой из этих культур, с тем чтобы получить максимальную прибыль.

Задача 12. На заводе используется сталь трех марок: А, В, С, запасы которых равны соответственно 10, 16 и 12 ед. Завод выпускает два вида изделий. Для изделия 1 требуется по одной единице стали всех марок. Для изделия 2 требуется 2 единицы стали марки В, одна – марки С и не требуется сталь марки А. От реализации единицы изделия вида 1 завод получает 300 руб. прибыли, а вида 2 – 200 руб. Составить план выпуска продукции, дающий наибольшую прибыль

Задача 13. Производитель безалкогольных напитков располагает двумя разливочными машинами А и В. Машина А спроектирована для пол-литровых бутылок, а машина В – для литровых. Машина А выпускает 50 пол-литровых бутылок в 1 мин, а машина В – 30 литровых бутылок в 1 мин. Каждая из машин работает ежедневно по 6 час, при пятидневной рабочей неделе. Прибыль от пол-литровой бутылки составляет 4 цента, а от литровой – 10 центов. Недельная продукция не может превосходить 250000 л; рынок принимает не более 300000 пол-литровых бутылок и 200000 литровых. Сколько бутылок пол-литровых и литровых необходимо выпускать производителю, чтобы максимизировать свою прибыль при имеющихся средствах.

Литература

1. Таха Х. Введение в исследование операций, в 2-х книгах. Пер. с англ.. – М.: Мир, 1985

2. Акулич И.Л. Математическое программирование в примерах и задачах. – М.: Высш. Шк., 1986

3. Шикин Е.В., Чхартишвили А.Г. Математические методы и модели в управлении. – М., Дело, 2002

4. Банди Б. Основы линейного программирования. Пер. с англ. – М.: Радио и связь, 1989